package com.wangwan.suanfa;

public class TravelingSalesmanBacktracking {

    private static int minDistance = Integer.MAX_VALUE; // 保存最小路径长度

    // 主方法：调用回溯算法计算最短路径
    public static int tspBacktracking(int[][] graph) {
        int n = graph.length; // 城市数量
        boolean[] visited = new boolean[n]; // 标记城市是否已访问
        visited[0] = true; // 从第一个城市开始
        backtrack(graph, visited, 0, 0, 1, n); // 开始回溯
        return minDistance;
    }

    /**
     * 回溯算法
     * @param graph 城市距离矩阵
     * @param visited 标记已访问的城市
     * @param currentCity 当前城市
     * @param currentDistance 当前路径长度
     * @param count 已访问的城市数量
     * @param totalCities 总城市数量
     */
    private static void backtrack(int[][] graph, boolean[] visited, int currentCity, int currentDistance, int count, int totalCities) {
        // 如果所有城市都访问过了，回到起点，更新最小路径
        if (count == totalCities) {
            minDistance = Math.min(minDistance, currentDistance + graph[currentCity][0]);
            return;
        }

        // 遍历所有城市，尝试访问未访问的城市
        for (int nextCity = 0; nextCity < totalCities; nextCity++) {
            if (!visited[nextCity]) {
                visited[nextCity] = true; // 标记城市为已访问
                backtrack(graph, visited, nextCity, currentDistance + graph[currentCity][nextCity], count + 1, totalCities);
                visited[nextCity] = false; // 回溯，恢复状态
            }
        }
    }

    public static void main(String[] args) {
        // 城市距离矩阵 (对称图，graph[i][j] = 两城市间的距离)
        int[][] graph = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };

        int result = tspBacktracking(graph);
        System.out.println("最短路径的总距离：" + result);
    }
}
